/**
 * 
 */
package cn.edu.ustc.multicore.exercise.ch1;

/**
 * @author dragon
 * 
 */
public class PrimeSearching extends Thread {

	// search scope
	private long from = 0;
	private long to = 0;
	// how many prime in scope
	private long count = 0;

	private Divider divider = null;

	public PrimeSearching(Divider divider) {
		this.divider = divider;
	}

	public PrimeSearching(long start, long end) {
		this.from = start;
		this.to = end;
	}

	public static boolean isPrime(long number) {
		if (number < 2) {
			return false;
		}
		for (long i = 2; i <= Math.sqrt(number); i++) {
			if (number % i == 0 && number != 2) {
				return false;
			}
		}
		return true;
	}

	public long getCount() {
		return count;
	}

	public void run() {
		if (divider == null) {
			// scan all number from start to end without divider
			long gap = to - from;
			if (gap < 0)
				return;
			for (long number = from; number < to; number++) {
				if (isPrime(number))
					count++;
			}
		} else {
			boolean running = true;
			while (running) {
				long number = divider.assignNumber();
				if (number > 0 && number< divider.end) {
					if (isPrime(number))
						count++;
				} else {
					running = false;
				}
			}
		}
	}

	/**
	 * 
	 * @param start
	 * @param end
	 * @param count
	 * @param usedTime
	 */
	public static void printResult(long start, long end, long count,
			String program, int threads, double usedTime) {
		System.out.println("the result of prime seaching as below: ");
		System.out.println("---------------------------------------");
		System.out.println("-> searching scope: (" + start + "~" + end + ")");
		System.out.println("-> total prime count: " + count);
		System.out.println("-> used programming: " + program);
		System.out.println("-> used threads: " + threads);
		System.out.println("-> used time(s): " + usedTime);
		System.out.println("---------------------------------------\n\n");
	}
/**
 * 
 * @author dragon
 *
 */
	static class Divider {
		private long start = 0l;
		private long end = 0l;
		private long current = 0l;
		private Object lock = new Object();

		public Divider(long start, long end) {
			this.start = start;
			this.end = end;
			this.current = start;
		}

		/**
		 * get a number ,if all number has been divided, return -1
		 */
		public long assignNumber() {
			synchronized (lock) {
				current++;
				if (current < end)
					return current;
				else
					return -1;
			}
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		//the thread number to run 
		int threads = 2;
		//the index of power about search scope, such as 10 power 6(index) 
		int index = 6;
		// algorithm method: sequential program, parallel program, concurrent
		// program
		String algName = null;

		long startTime = 0l;

		long endTime = 0l;

		long totalCount = 0;

		double usedSecond = 0.0;
		
		//parse the parameter, and assign them
		if(args != null & args.length>0){
			boolean correct = true;	
			for(int i =0; i< args.length; i++){
				if("-threads".equals(args[i])){
					if(args[i+1] != null){
						threads = Integer.valueOf(args[i+1]);
						i++;
						continue;
					}else{
						correct = false;
						break;
					}
				}
				
				if("-index".equals(args[i])){
					if(args[i+1] != null){
						index = Integer.valueOf(args[i+1]);
	                    i++;
	                    continue;
					}else{
						correct = false;
						break;
					}
				}
				correct = false;
				break;
				
			}
			
			if(!correct){
				System.out.println("Usage: "+PrimeSearching.class.getName() +" -threads n -index m ");
				return ;
			}
		}
		
		// the begin of scope to search
		long start = 0;
		// the end of scope to search
		long end = (long) Math.pow(10, index) * 1;

		/*
		 * 1. sequential search, it means single thread
		 */
		startTime = System.currentTimeMillis();
		algName = "sequential program";
		for (long i = start; i < end; i++) {
			if (isPrime(i)) {
				totalCount++;
			}
		}
		endTime = System.currentTimeMillis();
		usedSecond = (double)(endTime - startTime) / 1000;
		printResult(start, end, totalCount, algName, 1, usedSecond);

		/*
		 * 2. parallel search with static division
		 */
		// reset setting
		start = 0;
		algName = "parallel program";
		end = (long) Math.pow(10, index) * 1;
		totalCount = 0;

		startTime = System.currentTimeMillis();
		try {
			PrimeSearching[] ps = new PrimeSearching[threads];
			long from = start;
			long to = end;
			for (int i = 0; i < threads; i++) {
				// divide the scope into segments
				long step = (end - start) / threads;
				if (i < threads - 1) {
					to = from + step;
				} else {
					// last segment
					to = end;
				}
				ps[i] = new PrimeSearching(from, to);
				ps[i].start();
				from = to;
			}
			for (int i = 0; i < threads; i++) {
				ps[i].join();
				totalCount += ps[i].getCount();

			}
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		endTime = System.currentTimeMillis();
		usedSecond = (double)(endTime - startTime) / 1000;
		printResult(start, end, totalCount, algName, threads, usedSecond);

		/*
		 * 3. concurrent search with dynamic division
		 */
		start = 0;
		algName = "concurrent program with multithread";
		end = (long) Math.pow(10, index) * 1;
		totalCount = 0;
		Divider divider = new Divider(start, end);
		startTime = System.currentTimeMillis();
		try {
			PrimeSearching[] ps = new PrimeSearching[threads];
			for (int i = 0; i < threads; i++) {
				// divide the scope into segments with divider

				ps[i] = new PrimeSearching(divider);
				ps[i].start();
	
			}
			for (int i = 0; i < threads; i++) {
				ps[i].join();
				totalCount += ps[i].getCount();

			}
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		endTime = System.currentTimeMillis();
		usedSecond = (double)(endTime - startTime) / 1000;
		printResult(start, end, totalCount, algName, threads, usedSecond);
	}

}
